//
// Created by Administrator on 2021/5/21.
//
#include <vector>
#include <queue>
#include <iostream>
#include <set>

using namespace std;

class Solution {
public:
    int kthSmallest(vector<vector<int>> &mat, int k) { // 暴力
        int m = (int) mat.size();
        vector<int> res(mat[0]); // 第一行
        for (int i = 1; i < m; ++i) { // 遍历行
            multiset<int> st; // 一个有序set
            for (int x:res) {
                for (int y:mat[i]) { // 新一行的每个数都和res元素加和
                    st.insert(x + y);
                }
            }
            res.assign(st.begin(), st.end());
            res.resize(min(k, (int) res.size())); // 取前k个
        }
        return res[k - 1];
    }
};

#define MP make_pair
#define PAIR pair<int,vector<int>>

class Solution1 {
public:
    struct cmp {
        bool operator()(const PAIR &a, const PAIR &b) {
            return a.first > b.first; // 小根堆
        }
    };

    int kthSmallest(vector<vector<int>> &mat, int k) {
        //PAIR的 first：{sum(mat[i][second[i]])   0<=i<n}  ；second[i]=index ：第i+1行选择下标为index的数
        priority_queue<PAIR, vector<PAIR>, cmp> q;
        //repeat查重 每种状态只遍历一次  状态就是每行选择的数的下标  在second中保存
        set<vector<int> > repeat;
        int m = (int) mat.size(), n = (int) mat[0].size();
        int init = 0;
        //init是每行都选择第一个 一定是就是最小的
        for (auto &i:mat) init += i.front();
        //push起始状态   sum=init   m行，每一行选择的下标都是0
        q.push(MP(init, vector<int>(m, 0)));
        for (int j = 1; j < k; ++j) {
            auto temp = q.top();
            q.pop();
            for (int i = 0; i < m; ++i)
                if (temp.second[i] + 1 < n)  //如果第i行的下标  +1之后不会越界
                {
                    vector<int> temp_v = temp.second;
                    //新的状态 第i行的选择后移一步
                    temp_v[i] += 1;
                    //如果这种状态已经到达过了 continue
                    if (!repeat.insert(temp_v).second) continue;
                    // 更新sum 并push
                    int sum = temp.first + mat[i][temp_v[i]] - mat[i][temp_v[i] - 1];
                    q.push(MP(sum, temp_v));
                }
        }
        return q.top().first;
    }
};

class Solution3 { // 二分
public:
    vector<vector<int>> temp;
    int m=0, n=0;

    int kthSmallest(vector<vector<int>> &mat, int k) {
        temp = mat;
        m = (int) mat.size(), n = (int) mat[0].size();
        int left = 0, right = 0;
        for (int i = 0; i < m; i++) left += mat[i][0], right += mat[i].back();
        int init = left;
        while (left < right) {
            int mid = (left + right) / 2;
            int num = 1;   // 有多少个组合和小于当前值
            dfs(mid, 0, init, num, k);
            if (num >= k) right = mid;
            else left = mid + 1;
        }
        return left;
    }

    void dfs(int mid, int index, int sum, int &num, int k) {
        /**统计和小于mid 的组合数量
         * mid 是当前的上限
         * index是第几行
         * sum是求和的值
         * &num 计算个数
         */
        if (sum > mid || index == m || num > k) return;
        dfs(mid, index + 1, sum, num, k);
        for (int i = 1; i < n; i++) { // 列遍历
            if (sum + temp[index][i] - temp[index][0] <= mid) {
                num++; // 每次都是为了更新num
                dfs(mid, index + 1, sum + temp[index][i] - temp[index][0], num, k); // 下一行
            } else {
                break;
            }
        }
    }
};

int main() {
    Solution3 sol;
    vector<vector<int>> mat{{1, 3, 11},
                            {2, 4, 6}};
    cout << sol.kthSmallest(mat, 5) << endl;
    return 0;
}